class Node {
  constructor(key, left = null, right = null) {
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

Node.prototype.insert = function(root, key){
  if(!root) return new Node(key);

  if(key < root.key) root.left = this.insert(root.left, key);
  if(key > root.key) root.right = this.insert(root.right, key);

  return root;
}

Node.prototype.erase = function(root, key){
  if(!root) return;

  if(key < root.key){
    root.left = this.erase(root.left, key);
  }else if(key > root.key){
    root.right = this.erase(root.right, key);

  //说明该root是需要被删除的那个节点 （但我们不应该删除它的子节点，需要把它的子节点挂给这个root的父级）
  }else {
    if(!root.left && !root.right){ // 删除度为0
      delete root;
      return null;

    }else if(!root.left || !root.right){ // 删除度为1
      let temp = root.left ? root.left : root.right;
      delete root;
      return temp; //返回给上面↑ 让上面一层的 root.left 或者 right 接收了

    }else { // 删除度为2
      let tmp = getPre(root);
      root.key = tmp.key; //把root 替换为我们的前驱节点
      root.left = this.erase(root.left, tmp.key)
    }
  }

  return root;
}

function getPre(root){
  let node = root.left;
  while (node.right) node = node.right;
  return node;
}

//-------------------------------


let root = new Node(5);
root.insert(root, 9);
root.insert(root, 8);
root.insert(root, 3);
root.insert(root, 4);
root.insert(root, 15);
root.insert(root, 6);
root.insert(root, 2);
root.insert(root, 1);
root.erase(root, 3);
root.erase(root, 6);

function output(root){
  let ret = [];

  function inner(root){
    if(!root) return;
    inner(root.left);
    ret.push(root.key);
    inner(root.right);
  }

  inner(root);

  console.log(ret.join(','));
}

output(root)
